|
In mathematics and computer science, a matroid oracle is a subroutine through which an algorithm may access a matroid, an abstract combinatorial structure that can be used to describe the linear dependencies between vectors in a vector space or the spanning trees of a graph, among other applications. The most commonly used oracle of this type is an independence oracle, a subroutine for testing whether a set of matroid elements is independent. Several other types of oracle have also been used; some of them have been shown to be weaker than independence oracles, some stronger, and some equivalent in computational power.〔; ; .〕 Many algorithms that perform computations on matroids have been designed to take an oracle as input, allowing them to run efficiently without change on many different kinds of matroids, and without additional assumptions about what kind of matroid they are using. For instance, given an independence oracle for any matroid, it is possible to find the minimum weight basis of the matroid by applying a greedy algorithm that adds elements to the basis in sorted order by weight, using the independence oracle to test whether each element can be added.〔.〕 In computational complexity theory, the oracle model has led to unconditional lower bounds proving that certain matroid problems cannot be solved in polynomial time, without invoking unproved assumptions such as the assumption that P ≠ NP. Problems that have been shown to be hard in this way include testing whether a matroid is binary or uniform, or testing whether it contains certain fixed minors.〔.〕 ==Why oracles?== Although some authors have experimented with computer representations of matroids that explicitly list all independent sets or all basis sets of the matroid,〔.〕 these representations are not ''succinct'': a matroid with elements may expand into a representation that takes space exponential in . Indeed, the number of distinct matroids on elements grows doubly exponentially as :〔; ; ; .〕 from which it follows that any explicit representation capable of handling all possible matroids would necessarily use exponential space.〔.〕 Instead, different types of matroids may be represented more efficiently from the other structures from which they are defined: uniform matroids from their two numeric parameters, graphic matroids, bicircular matroids, and gammoids from graphs, linear matroids from matrices, etc. However, an algorithm for performing computations on arbitrary matroids needs a uniform method of accessing its argument, rather than having to be redesigned for each of these matroid classes. The oracle model provides a convenient way of codifying and classifying the kinds of access that an algorithm might need. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「matroid oracle」の詳細全文を読む スポンサード リンク
|